class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        
        // 按 w 升序，h 降序
        auto cmp = [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        };
        sort(envelopes.begin(), envelopes.end(), cmp);
        
        // 按 w 升序，且 h 降序后，我们只需要看 h 的最长递增子序列的长度即可
        // why?
        // e.g heights = [[2, 3], [5, 4], [5, 6], [6, 7]]
        // h 的最长递增子序列是[3, 4, 6, 7]，是 4，但是很明显是 3，因为[5, 4]放不进[5, 6]里面
        // 所以，当 w 相同时，按 h 的降序排列，并且不影响后续结果，因为不论[5, 4]还是[5, 6]都可以放进[6, 7]里面去
        // 下面采用贪心的策略，时间复杂度是O(NlogN)
        vector<int> ret;
        ret.push_back(envelopes[0][1]);
        for(int i = 1; i < n; i++)
        {
            if(envelopes[i][1] > ret.back())
                ret.push_back(envelopes[i][1]);
            else
            {
                // 二分
                int left = 0, right = ret.size() - 1;
                while(left < right)
                {
                    int mid = (left + right) >> 1;
                    if(ret[mid] < envelopes[i][1])
                        left = mid + 1;
                    else
                        right = mid;
                }
                ret[left] = envelopes[i][1];
            }
        }
        return ret.size();
    }
};